#include "Astar.h"
#include <sstream>
#include <cmath>
#include <queue>

astar::astar() {
    std::cout << "initial map:" << std::endl;
    std::string line;
    while (std::getline(std::cin, line) && !line.empty()) {
        std::stringstream ss(line);
        int num;
        std::vector<node> row;
        while (ss >> num) {
            node a;
            a.za = num;
            a.x = map.size();
            a.y = row.size();
            row.push_back(a);
        }
        map.push_back(row);
    }
}

int astar::djh(const node& x) const {
    return x.zs + std::abs(final->x - x.x) + std::abs(final->y - x.y);
}

void astar::search() {
    std::priority_queue<node> q;
    start->zs = 0;
    start->dj = djh(*start);
    start->closed_list=1;
    q.push(*start);

    int fx[8] = {0, 0, 1, -1, 1, -1, -1, 1};
    int fy[8] = {1, -1, 0, 0, -1, -1, 1, 1};
    int jl[8] = {2, 2, 2, 2, 3, 3, 3, 3};

    while (!q.empty()) {
        node f = q.top();
        q.pop();
       
        map[f.x][f.y].closed_list=1;
        for (int i = 0; i < 8; i++) {
            int ffx = f.x + fx[i];
            int ffy = f.y + fy[i];
            if (ffx== final->x && ffy == final->y) {
                map[ffx][ffy].parent=&map[f.x][f.y];
            out();
            return;
        }
            if (ffx >= 0 && ffx < map.size() && ffy >= 0 && ffy < map[0].size() && map[ffx][ffy].za != 0) {
                if (map[ffx][ffy].closed_list) continue;
                    int new_zs = f.zs + jl[i];
                   if(new_zs<map[ffx][ffy].zs){
                    map[ffx][ffy].zs = new_zs;
                    map[ffx][ffy].parent = &map[f.x][f.y];
                    map[ffx][ffy].dj=djh(map[ffx][ffy]);
                     if(!map[ffx][ffy].open_list){
                        q.push(map[ffx][ffy]);
                        map[ffx][ffy].open_list=1;
                   }
                   }
                  
            } 
        }
    }
}

void astar::init() {
    std::cout << "start:" << std::endl;
    int x1, y1;
    std::cin >> x1 >> y1;
    start = &map[x1][y1];
    std::cout << "final:" << std::endl;
    std::cin >> x1 >> y1;
    final = &map[x1][y1];
}

void astar::out() {
    std::vector<node*> ans;
    node* a = final;
    // if(final->parent!=nullptr)std::cout<<final->parent->x<<" "<<final->parent->y; 测试
    while (a != start && a != nullptr) {
        ans.push_back(a);
        a = a->parent;
    }
    if (a == nullptr&&a!=start->parent) {
        std::cout << "No path found." << std::endl;
        return;
    }
    std::cout << "(" << start->x << "," << start->y << ") ";
    for (int i = ans.size() - 1; i >= 0; i--) {
        map[ans[i]->x][ans[i]->y].ans=1;
        std::cout << "(" << ans[i]->x << "," << ans[i]->y << ") ";
    }
    std::cout << std::endl;
}
void astar::mapout(){
    for(int i=0;i<map.size();i++){
        for(int j=0;j<map[i].size();j++){
            if(!map[i][j].ans)std::cout<<map[i][j].za<<" ";
            else std::cout<<"* ";
        }
        std::cout<<std::endl;
    }

}